#include "movingCount.h"
int bitSum(int a)
{
    int res = 0;
    while (a > 0)
    {
        res += a % 10;
        a /= 10;
    }
    return res;
}

int movingCount(int m, int n, int k)
{
    if (!k)
        return 1;

    vector<vector<int>> visited(m, vector<int>(n, 0));
    int res = 0;
    for (int r = 0; r < m; r++)
    {
        for (int c = 0; c < n; c++)
        {
            if (r == 0 && c == 0)
            {
                res = 1;
                visited[r][c] = 1;
                continue;
            }
            if (bitSum(r) + bitSum(c) > k)
                continue;
            else
            {
                if (r - 1 >= 0)
                    visited[r][c] |= visited[r - 1][c];
                if (c - 1 >= 0)
                    visited[r][c] |= visited[r][c - 1];
                res += visited[r][c];
            }
        }
    }
    return res;
}